package start.ALG;

import org.junit.Test;

public class Path {

    @Test
    public void t0() {
        int[][] grid = new int[][]{
                {2,1,1,4},
                {1,2,3,3},
                {3,2,1,2},
                {3,2,1,2},
        };
        int width = grid[0].length, high = grid.length;
        // 初始化,计算出两边的固定步长
        for (int i = 1; i < high; i++)
            grid[i][0] += grid[i - 1][0];
        for (int i = 1; i < width; i++)
            grid[0][i] += grid[0][i - 1];
        //开始计算到每个点的最小步长并保存在点位上,步长等于上方或者左方的小值加上本身，每层计算，从左到右
        for (int i = 1; i < high; i++)
            for (int j = 1; j < width; j++)
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
        System.out.println(grid[high - 1][width - 1]);
    }
}
